package course.p10_heap;

/**
 * 普通堆结构，定义：
 * 堆是一颗具有特定性质的完全二叉树，注意，堆必须是完全二叉树哦
 * 这个特定性质是： 所有节点的值必须大于等于其孩子节点(最大堆) 或 小于等于其孩子节点(最小堆)
 *
 */
public class NorHeap {

    /**
     * 使用数组存储元素
     */
    public int[] array;

    /**
     * 堆中的元素个数
     */
    public int count;

    /**
     * 存储堆的空间大小
     */
    public int capacity;//堆的大小

    /**
     * 堆的类型  1--最大堆  2--最小堆
     */
    public int heap_type;

    //创建堆构造方法
    public NorHeap(int capacity,int heap_type) {
        this.capacity = capacity;
        this.heap_type = heap_type;
        this.count = 0;
        this.array = new int[capacity];
    }

    /**
     * 得到index位置节点的父节点的索引
     * @param index
     * @return
     */
    public int parent(int index) {
        if(index<=0||index>this.count)
            return -1;
        return (index-1)/2;
    }


    /**
     * 得到索引位置节点的左孩子的索引
     * @param index
     * @return
     */
    public int leftChild(int index) {
        int left = 2*index+1;
        if(left >= this.count)
            return -1;
        return left;
    }


    /**
     * 得到索引位置节点的右孩子的索引
     * @param index
     * @return
     */
    public int rightChild(int index) {
        int right = 2*index+2;
        if(right >= this.count)
            return -1;
        return right;
    }


    //获取最大元素
    public int getMaximum() {
        if(this.count==0)
            return -1;
        return this.array[0];
    }

    //堆化元素

    /**
     * 节点堆化
     * @param i
     */
    public void percolateDown(int i) {
        int left,right,max,temp;
        // i的左孩子位置
        left = leftChild(i);
        // i的右孩子
        right = rightChild(i);
        if(left==-1&&right==-1)
            return;
        if(left!=-1&&this.array[left]>this.array[i])
            max = left;
        else
            max = i;
        if(right!=-1&&this.array[right]>this.array[max])
            max = right;

        if(max==i)
            return;
        else {
            temp = this.array[i];
            this.array[i] = this.array[max];
            this.array[max] = temp;
        }
        percolateDown(max);
    }


    /**
     * 删除并返回堆的最大元素
     * @return
     */
    int deleteMax() {
        if(this.count==0)
            return -1;
        int data = this.array[0];
        this.array[0] = this.array[this.count-1];
        this.count--;
        percolateDown(0);
        return data;
    }

    /**
     * 向堆中添加元素
     * @param data
     */
    void insert(int data) {
        int i;
        if(this.count==this.capacity)
            resizeHeap();
        this.count++;
        i=this.count-1;
        //不断找到比自己小的父母节点交换之
        while(i>=0&&data>this.array[(i-1)/2]) {
            this.array[i]=this.array[(i-1)/2];
            i=(i-1)/2;
        }
        this.array[i]=data;
    }

    /**
     * 扩容方法
     */
    void resizeHeap() {
        int[] array_old = new int[this.capacity];
        System.arraycopy(this.array,0,array_old,0,this.count);
        this.array = new int[this.capacity*2];
        if (this.capacity >= 0)
            System.arraycopy(array_old, 0, this.array, 0, this.capacity);
        this.capacity *=2;
    }


    /**
     * 清空堆
     */
    void destroyHeap() {
        this.count=0;
        this.array=null;
    }


    //数组建堆
    void BuildHeap(NorHeap h,int[] array,int n) {
        if(h==null) return;
        // 容量扩容
        while(n > this.capacity) h.resizeHeap();
        //数组赋值
        if (n >= 0) System.arraycopy(array, 0, h.array, 0, n);
        this.count = n;
        //节点堆化
        for(int i=(n-2)/2;i>=0;i--)
            h.percolateDown(i);
    }

    /**
     * 堆排序
     * @param array 需要排序的数组
     */
   public static void heapSort(int[] array) {
        NorHeap h = new NorHeap(array.length,1);
        int i, temp;
        h.BuildHeap(h,array,array.length);

        for(i = array.length-1;i >= 0;i--){
            temp = h.array[0];
            array[i] = temp;
            h.array[0] = h.array[h.count-1];
            h.count--;
            h.percolateDown(0);
        }
   }

}



